1. Field of the Invention
The present invention generally relates to the field of dynamic memory allocation in a networking protocol handler, and, more particularly, to a method and apparatus for dynamically allocating memory between inbound and outbound paths of a protocol handler so as to optimize the ratio of a given amount of memory between the inbound and outbound memory buffers.
2. Background Description
Computer networks are based on the linking of two or more computers for sharing files and resources or for otherwise enabling communications and data transfer between the computers. The computers, often referred to as network nodes, are coupled together through various hardware network devices that allow data to be received, stored and then sent out across the network. Apart from the computers themselves, examples of such network devices requiring the ability to transfer data include controllers, bridges, switches and routers. The foregoing also applies to virtually any addressable point on a network and, in particular, to other devices connected to the network containing microcontrollers (e.g., printers, storage devices).
Because the data communications cannot occur instantaneously and/or because it is often desirable to control the data transfer, memory buffers are used for receiving, storing and sending the data to/from the network node. Memory buffers are essentially temporary memory locations that are used in the process of forwarding data to/from an input port from/to an output port. Requirements placed on the memory buffers increase when the network system employs bi-directional communications and when the inbound and outbound processing of data is simultaneous (i.e., full-duplex). Transfer of data into or out of the memory buffers is performed according to certain networking protocols. Such networking protocols employ flow control algorithms to ensure the transmitting station does not overwhelm the receiving node with data. The same is true for controlling the flow of data out of the network node.
The traditional approach for memory buffers includes an inbound buffer and an outbound buffer for receiving, storing and sending data packets (also referred to as “data frames”). One common buffer can also be used for both incoming and outgoing data transmission, provided the data input/output is not simultaneous. In any event, a certain amount of buffer memory is dedicated to receiving data into the network node (the inbound buffer) and to sending data out of the network node (the outbound buffer).
The advantage of using a common buffer is that the amount of space dedicated to the inbound versus the outbound paths can be easily configured through register programming when initializing the hardware. The drawback is that there is access contention to the memory buffer between the inbound and outbound paths that can result in significant performance degradation when simultaneously processing inbound and outbound frames. Also, for maximum performance the memory buffer access bandwidth must match the combined bandwidth of the inbound network link, the outbound network link, the inbound host interface, the outbound host interface, and any processing overhead. With modern network link speeds well in excess of 100 Mbytes/sec and host bus speeds even greater this may require wide memory data paths and large FIFO's on the network side. Separating the memory into inbound and outbound buffers improves performance by reducing the memory access contention but forces the ratio of inbound to outbound buffer space to be fixed at design time. A method for combining the advantages of both of these options is needed.
The proper allocation of memory between the inbound and outbound buffers for receiving or sending data packets is always a consideration for controller (protocol handler) designers. Though increased buffer space equates to better performance, over-allocating buffer memory results in higher costs. Unfortunately, however, there are many application-dependent factors that impact the memory requirements for a protocol handler. These include the average size of the data packets and the ratio of inbound to outbound traffic seen by the protocol handler. Also, the system requirements will differ depending upon whether the network is primarily an originator or a responder. As a result, for a given amount of memory, designers cannot optimize the ratio of inbound to outbound memory at the design stage.
When buffer space is underutilized in a particular application a potential cost savings is not realized. When buffer space is insufficient the result is a loss of system performance due to the throttling of the frame rate (flow control) on the network. In the case of the outbound buffer being too small the frame transmission rate is limited by the sending node. When the inbound buffer is too small it is the receiving node which limits the rate. Also, depending on the type of network, there may be overhead associated with the flow control mechanism to relinquish and rearbitrate for a shared bus.
For some systems, where the traffic on the links is not bi-directional and/or where simultaneous inbound and outbound processing is not required, a single fixed amount of memory would suffice. Such systems include asynchronous transfer mode (ATM) switches where the frame (referred to as a “cell” in ATM terminology) size is fixed and the bandwidth is symmetric, that is the inbound bandwidth is equal to the outbound bandwidth. In these systems inbound cells can be routed to any buffer in a pool of fixed size buffers. From this buffer the cell can be directly routed to the appropriate outbound path with the routing being based on the cell header contents. Such a system is described in PCT patent WO 00/52955 that teaches a method for assigning memory buffer units to a particular input of a network communication device based on port utilization and quality of service goals. In that patent, the system includes a plurality of memory buffers, each divided into several sub-pools, and a buffer allocator is used for allocating buffer units between the sub-pools. The buffer allocator is arranged to operate based on a quality of service parameter and on a utilization value so as to minimize loss of data transmission at the most heavily-utilized input ports. There are several key differences between this system and the one described in the present invention. ATM systems use small fixed size cells so there is no need to perform calculations on free blocks to determine if another cell can be received. Furthermore, flow control is not used, rather, cells are allowed to be dropped when congestion occurs. WO 00/52955 is concerned with minimizing the number of dropped packets during congestion.
Another difference is that ATM switches and routers have symmetric input and output bandwidth requirements. Cells received into a buffer on the inbound path will be transmitted out of the same buffer on the outbound path. In effect, a single buffer resides in both the inbound and the outbound paths so no reallocation of the buffer space is needed. Also, to minimize costs, a design may incorporate a fixed amount of buffer memory that is not dynamically allocable between the inbound and outbound paths. However, such an approach may induce memory access bottlenecks in the traffic flow for certain applications.
In previous network protocol controllers, for example the Agilent HPFC-5166 Tachyon TS PCI to Fibre Channel Controller, separate frame buffers are used for the inbound and outbound paths. In the Tachyon architecture the inbound and outbound FIFO's are sized large enough to also serve as the frame buffers. The inbound FIFO can hold a maximum of four 2K-byte frames and the outbound FIFO can hold one maximum-size frame. The FIFO sizes are fixed and there is no borrowing of excess space by one FIFO from another.
Similarly, the Qlogic ISP2200 contains separate on-chip inbound and outbound frame buffer spaces. These buffers only support one 2112 byte frame payload, however an interface to optional external memory is provided as a means for increasing the buffer space. In this way buffer sizes can be selected at system design time, however there is not way to statically or dynamically partition the available memory between the inbound and outbound paths once the system or card is built. Since network traffic is bursty and unpredictable it is desirable to be able to dynamically repartition the buffer space in response to the changing network traffic.
Each of the aforementioned systems suffers from the same drawback, that is, for a fixed amount of memory, being unable to dynamically allocate memory between the inbound and outbound buffers of a network protocol handler. As a result, memory access bottlenecks occur in data communications and/or memory buffers must be over-designed to accommodate the peak load expected to be seen by the network.